package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         525,
		Discription: "找到含有相同数量的 0 和 1 的最长连续子数组",
		Level:       2,
		Labels: map[string]int{
			"前缀和": 1,
			"哈希表": 1,
		},
	})
}

func FindMaxLength(nums []int) int {
	prefixSumMap := make(map[int]int, 0)
	sum := 0
	maxLen := 0
	//把0当成-1，问题转化为和为0的最长子数组
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			sum--
		} else {
			sum++
		}

		//如果等于0，直接返回
		if sum == 0 {
			maxLen = max(maxLen, i+1)
			continue
		}

		if prefixEnd, exist := prefixSumMap[sum]; exist {
			maxLen = max(i-prefixEnd, maxLen)
			//记得continue，map中对应值的结束位置越靠越好，当前的肯定比之前存的靠后
			continue
		}

		prefixSumMap[sum] = i
	}

	return maxLen
}
